|
A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the Fibonacci sequence. The Fibonacci sequence may be described by the recurrence relation: : Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence: : In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2M), often 232 or 264. The operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise arithmetic exclusive-or operator (XOR). The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for j and k. These generators also tend to be very sensitive to initialisation. Generators of this type employ k words of state (they 'remember' the last k values). If the operation used is addition, then the generator is described as an ''Additive Lagged Fibonacci Generator'' or ALFG, if multiplication is used, it is a ''Multiplicative Lagged Fibonacci Generator'' or MLFG, and if the XOR operation is used, it is called a ''Two-tap generalised feedback shift register'' or GFSR. The Mersenne twister algorithm is a variation on a GFSR. The GFSR is also related to the linear feedback shift register, or LFSR. == Properties of lagged Fibonacci generators == Lagged Fibonacci generators have a maximum period of (2k - 1) *2M-1 if addition or subtraction is used, and (2k-1) *k if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2k - 1) *2M-3, or 1/4 of period of the additive case. For the generator to achieve this maximum period, the polynomial: :y = xk + xj + 1 must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. Popular pairs are: :, , , , (), , , , , , , , () Another list of possible values for ''j'' and ''k'' is on page 29 of volume 2 of ''The Art of Computer Programming'': :(24,55), (38,89), (37,100), (30,127), (83,258), (107,378), (273,607), (1029,2281), (576,3217), (4187,9689), (7083,19937), (9739,23209) Note that the smaller number have short periods (only a few "random" numbers are generated before the first "random" number is repeated and the sequence restarts). If addition is used, it is required that at least one of the first k values chosen to initialise the generator be odd; if multiplication is used, instead, it is required that all the first k values be odd.〔http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps〕 It has been suggested that good ratios between j and k are approximately the golden ratio.〔"Uniform random number generators for supercomputers", Richard Brent, Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 704-706〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lagged Fibonacci generator」の詳細全文を読む スポンサード リンク
|